<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>寻路算法</title>
    <style>
      .cell {
        width: 6px;
        height: 6px;
        background-color: gray;
        border-right: 1px solid #fff;
        border-bottom: 1px solid #fff;
        vertical-align: middle;
        display: inline-block;
      }
      .active {
        background-color: #000;
      }
      .container {
        width: 700px;
        font-size: 0;
      }
      .lightgreen {
        background-color: lightgreen;
      }
      .pathpink {
        background-color: pink;
      }
    </style>
  </head>
  <body>
    <div class="container"></div>
    <button id="save">保存</button>
    <button id="findPath">寻路</button>
    <script>
      class Sorted {
        constructor(data, compare) {
          this.data = data;
          this.compare = compare;
        }
        take() {
          if (!this.data.length) {
            return;
          }
          let min = this.data[0];
          let minIndex = 0;
          for (let i = 0; i < this.data.length; i++) {
            const item = this.data[i];
            if (this.compare(this.data[i], min) < 0) {
              min = this.data[i];
              minIndex = i;
            }
          }
          this.data[minIndex] = this.data[this.data.length - 1];
          this.data.pop();
          return min;
        }
        push(item) {
          this.data.push(item);
        }
        get length() {
          return this.data.length;
        }
      }
    </script>
    <script>
      // 创建map数组
      let map = localStorage.getItem("map")
        ? JSON.parse(localStorage.getItem("map"))
        : Array(10000).fill(0);
      // 创建dom结构
      const container = document.getElementsByClassName("container")[0];
      const fg = document.createDocumentFragment();
      for (let y = 0; y < 100; y++) {
        for (let x = 0; x < 100; x++) {
          const cell = document.createElement("div");
          cell.classList.add("cell");
          cell.dataset.map = [x, y].join();
          if (map[y * 100 + x] === 1) {
            cell.classList.add("active");
          }
          fg.appendChild(cell);
        }
      }
      container.appendChild(fg);
      // 事件处理
      let isMouseDown = false;
      let isClear = false;
      document.addEventListener(
        "mousedown",
        (e) => {
          isMouseDown = true;
          isClear = e.which === 3;
        },
        false
      );
      document.addEventListener(
        "mouseup",
        (e) => {
          isMouseDown = false;
          isClear = false;
        },
        false
      );
      document.addEventListener(
        "mousemove",
        (e) => {
          const target = e.target;
          if (
            target.className.indexOf("cell") < 0 ||
            !(isMouseDown || isClear)
          ) {
            return false;
          }
          const [x, y] = target.dataset.map
            .split(",")
            .map((item) => Number(item));
          if (isMouseDown) {
            target.classList.add("active");
            map[y * 100 + x] = 1;
          }
          if (isClear) {
            target.classList.remove("active");
            map[y * 100 + x] = 0;
          }
        },
        false
      );
      document.addEventListener("contextmenu", (e) => e.preventDefault());

      // 保存
      document.getElementById("save").addEventListener("click", () => {
        localStorage.setItem("map", JSON.stringify(map));
      });

      function sleep(t) {
        return new Promise((resove) => {
          setTimeout(resove, t);
        });
      }

      // 寻路
      async function findPath(map, start, end) {
        let table = map.slice();
        // 运算距离
        function distanbce([x, y]) {
          return (x - end[0]) ** 2 + (y - end[1]) ** 2;
        }
        // 创建初始队列,start为初始点坐标，为数组
        let queue = new Sorted([start], (a, b) => distanbce(a) - distanbce(b));
        // 插入函数
        async function insert([x, y], pre) {
          // 障碍点
          if (table[y * 100 + x] !== 0) {
            return false;
          }
          // 边界检测
          if (x < 0 || y < 0 || x >= 100 || y >= 100) {
            return false;
          }
          table[y * 100 + x] = pre;
          container.childNodes[y * 100 + x].classList.add("lightgreen");
          queue.push([x, y]);
          await sleep(0);
        }
        // 循环队列
        while (queue.length) {
          // 当前点
          let [x, y] = queue.take();
          if (x === end[0] && y === end[1]) {
            let path = [];
            while (!(x === start[0] && y === start[1])) {
              path.push([x, y]);
              container.childNodes[y * 100 + x].classList.add("pathpink");
              [x, y] = table[y * 100 + x];
              await sleep(10);
            }
            container.childNodes[start[1] * 100 + start[0]].classList.add(
              "pathpink"
            );
            return path;
          }
          // 上
          await insert([x, y - 1], [x, y]);
          // 下
          await insert([x, y + 1], [x, y]);
          // 左
          await insert([x - 1, y], [x, y]);
          // 右
          await insert([x + 1, y], [x, y]);
          /**
           * 支持斜边
           **/
          // 左上
          await insert([x - 1, y - 1], [x, y]);
          // 左下
          await insert([x - 1, y + 1], [x, y]);
          // 右上
          await insert([x + 1, y - 1], [x, y]);
          // 右下
          await insert([x + 1, y + 1], [x, y]);
        }
        return null;
      }
      let path = [];
      // 重新执行
      function reset() {
        // for (let i = 0; i < path.length; i++) {
        //   const [x, y] = path[i];
        //   container.childNodes[y * 100 + x].classList.remove(
        //     "lightgreen",
        //     "pathpink"
        //   );
        // }
        for (let y = 0; y < 100; y++) {
          for (let x = 0; x < 100; x++) {
            container.childNodes[y * 100 + x].classList.remove(
              "lightgreen",
              "pathpink"
            );
          }
        }
      }
      document.getElementById("findPath").addEventListener(
        "click",
        async () => {
          reset();
          path = await findPath(map, [0, 0], [50, 50]);
          console.log(path);
        },
        false
      );
    </script>
  </body>
</html>
